package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，
 * 请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
 * <p>
 * 示例 1：
 * <p>
 * 输入：matrix =
 * [
 * [0,1,1,1],
 * [1,1,1,1],
 * [0,1,1,1]
 * ]
 * 输出：15
 * 解释：
 * 边长为 1 的正方形有 10 个。
 * 边长为 2 的正方形有 4 个。
 * 边长为 3 的正方形有 1 个。
 * 正方形的总数 = 10 + 4 + 1 = 15.
 *
 * @author caijinnan
 * @date 2020/3/19 10:28
 */
public class 统计全为1的正方形子矩阵 {
    @Test
    public void run() {
        int[][] matrix = {
                {1, 1, 1, 1},
                {0, 1, 1, 1},
                {1, 1, 1, 1},
                {1, 1, 0, 1}
        };
//        int[][] matrix = {
//                {0, 1, 1, 1},
//                {1, 1, 1, 1},
//                {0, 1, 1, 1}
//        };
        int result = countSquares(matrix);
        System.out.println(result);
    }

    //通过
    public int countSquares(int[][] matrix) {
        int yLength = matrix.length;
        int xLength = matrix[0].length;
        int maxSquareLength = Math.min(yLength, xLength);
        int[][] dp = new int[yLength][xLength];
        int sum = 0;
        for (int y = 0; y < yLength; y++) {
            for (int x = 0; x < xLength; x++) {
                if (matrix[y][x] == 0) {
                    continue;
                }
                for (int lineLength = 0; lineLength < maxSquareLength; lineLength++) {
                    if (x + lineLength >= xLength || y + lineLength >= yLength) {
                        continue;
                    }
                    if (checkByDp(y, x, lineLength, dp) || checkSquare(y, x, lineLength, matrix)) {
                        dp[y][x]++;
                    }
                }
                sum += dp[y][x];
            }
        }
        return sum;
    }

    /**
     * 根据已知求是否满足
     *
     * @param y
     * @param x
     * @param lineLength
     * @param dp
     * @return
     */
    private boolean checkByDp(int y, int x, int lineLength, int[][] dp) {
        int subX = x-lineLength;
        int subY = y-lineLength;
        if (subX >= 0 && subY >= 0) {
            if (dp[subY][subX] > lineLength + 1) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断以左上角坐标为(y,x)是否可以组成边长为lineLength的正方形
     *
     * @param y          y轴坐标
     * @param x          x轴坐标
     * @param lineLength 边长
     * @return true|false
     */
    private boolean checkSquare(int y, int x, int lineLength, int[][] matrix) {
        for (int yTemp = y; yTemp <= y + lineLength; yTemp++) {
            for (int xTemp = x; xTemp <= x + lineLength; xTemp++) {
                if (matrix[yTemp][xTemp] != 1) {
                    return false;
                }
            }
        }
        return true;
    }
}